package com.practice.sequence;

import java.util.Stack;

public class MaxRainContainer {
	public int hold(int[] a) {
		Stack<Bar> stack = new Stack<Bar>();
		int total = 0;
		for (int i=0; i<a.length; i++) {
			while (!stack.isEmpty() && stack.peek().height <= a[i]) {
				Bar b = stack.pop();
				int bottom = b.height;
				if (stack.isEmpty()) break;
				
				Bar left = stack.peek();
				int top = Math.min(left.height, a[i]);
				total += (i - left.x - 1) * (top - bottom);
			}
			stack.push(new Bar(i, a[i]));
		}
		
		return total;
	}
	
	class Bar {
		int x;
		int height;
		public Bar(int x, int height) {
			this.x = x;
			this.height = height;
		}
	}
	
	public int hold2(int[] a) {
		int h = 0;
		int N = a.length;
		for (int i=1; i<N; i++) if (a[i] > a[h]) h = i;
		
		int total = 0;
		int left = a[0];
		for (int i=1; i<h; i++) {
			if (a[i] > left) {
				left = a[i];
			}
			else {
				total += left - a[i];
			}
		}
		
		int right = a[N-1];
		for (int i=N-2; i>h; i--) {
			if (a[i] > right) {
				right = a[i];
			}
			else {
				total += right - a[i];
			}
		}
		
		return total;
	}
}
